#include"btree.h"
#include<stdlib.h>
#include<stdio.h>
void TreeInit(Tree* t,int size){
    t->nodeSize = size;
    t->nodes = (TreeNode*)malloc(sizeof(TreeNode)*size);
    t->root = NULL;
    return ;
}
 
void TreeDestroy(Tree* t){
    free(t->nodes);
    t->nodes = NULL;
    t->nodeSize = 0; 
    t->root = NULL;
}

TreeNode* TreeGetNode(Tree* t,int id){//根据节点来返回树节点的地址
    return &t->nodes[id];
}

void Visit(TreeNode* n){//用于访问传入的二叉树节点node 
    printf("%c",n->val);//还可以作别的事情，比如写入数据到文件
}

TreeNode* createRecursively(Tree* t,eleType a[],int size,int nodeid,eleType nullnode ){//Recursively:递归的
    /*
        Tree* t 树的指针
        eleType a[] 存储树节点值的数组，这是构建树的数据来源
        int size  数组大小，用于边界检查
        int nodeid  当前要创建的节点ID，用于确定在数组中的位置
        int nullnode 空节点标识，用于判断哪些位置应该是空节点
        另外:a[] 是用于按层序存储二叉树数据的输入数组，表示树的逻辑结构
    */
   //假设是按完全二叉树的层序存储
    if(nodeid>size||a[nodeid]==nullnode){
        //如果要添加的树的结点的索引是大于树的节点的个数的
        //或者当前位置的值表示这是一个空节点（不是空数组，而是值等于空节点标识）
        return NULL ;
    }
    TreeNode* newNode = TreeGetNode(t,nodeid);
    newNode->val = a[nodeid];
    newNode->left = createRecursively( t,a,size, 2*nodeid,nullnode );
    newNode->right = createRecursively( t,a,size, 2*nodeid + 1,nullnode);
    return newNode;
}

void TreeCreate(Tree* t,eleType a[],int size,eleType nullnode){
    //实际上在外部创建树的时候一定是从树的根节点开始的
    //把root的id设置为1
    t->root = createRecursively(t,a,size,1,nullnode);
}

void preOrder(Tree* t,TreeNode* node){//前序遍历树
    //顺序是 根 左 右
    if(node){//当前节点不为空
        Visit(node);
        preOrder(t,node->left);
        preOrder(t,node->right);
    }
}

// 提供给外部的调用时,可以消掉一个参量
void TreePreOrderTraversal(Tree* t){
    preOrder(t,t->root);
}//符合面向对象的封装思想，将复杂的实现细节隐藏在内部

void inOrder(Tree* t,TreeNode* node){//中序遍历
    if(node){//当前节点不为空
        inOrder(t,node->left);
        Visit(node);
        inOrder(t,node->right);
    }
}

void TreeInOrderTraversal(Tree* t){
    inOrder(t,t->root);
}

void postOrder(Tree* t,TreeNode* node){ //后序遍历
    if(node){//当前节点不为空
        postOrder(t,node->right);
        postOrder(t,node->left);
        Visit(node);
    }
}

void TreePostOrderTraversal(Tree* t){
    postOrder(t,t->root);
}
